﻿
/// <summary>
/// https://leetcode-cn.com/problems/sudoku-solver/
/// </summary>
public class Solution
{
    private class Block
    {
        public int X { get; }
        public int Y { get; }
        public int Value { get; set; }
        public Block(int x, int y)
        {
            this.X = x;
            this.Y = y;
            this.Value = 1;
        }
    }
    public void SolveSudoku(char[][] board)
    {
        List<Block> emptyBlocks = new List<Block>();
        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                if (board[i][j] == '.')
                    emptyBlocks.Add(new Block(i, j));
            }
        }

        int cur = 0;
        for (; cur < emptyBlocks.Count;)
        {
            bool found = false;
            int num = 0;
            for (int i = 1; i < 10; i++)
            {
                if (this.IsGood(emptyBlocks[cur].X, emptyBlocks[cur].Y, i, board))
                    num++;
                if (num == emptyBlocks[cur].Value)
                {
                    board[emptyBlocks[cur].X][emptyBlocks[cur].Y] = (char)(i + '0');
                    found = true;
                    break;
                }
            }
            if (found)
                cur++;
            else
            {
                emptyBlocks[cur].Value = 1;
                emptyBlocks[cur - 1].Value++;
                cur--;
                board[emptyBlocks[cur].X][emptyBlocks[cur].Y] = '.';
            }
        }
    }
    private bool IsGood(int x, int y, int val, char[][] board)
    {
        for (int i = 0; i < 9; i++)
        {
            if (board[i][y] == '.')
                continue;
            if (board[i][y] - '0' == val)
                return false;
        }
        for (int i = 0; i < 9; i++)
        {
            if (board[x][i] == '.')
                continue;
            if (board[x][i] - '0' == val)
                return false;
        }
        int startx, endx, starty, endy;
        startx = (x / 3) * 3;
        endx = startx + 3;
        starty = (y / 3) * 3;
        endy = starty + 3;
        for (int i = startx; i < endx; i++)
        {
            for (int j = starty; j < endy; j++)
            {
                if (board[i][j] == '.')
                    continue;
                if (board[i][j] - '0' == val)
                    return false;
            }
        }
        return true;
    }
}

/* 下方案超时（因为抄了上个数独项目，不想搞了，直接上了随机数，多次测试，结果正确，用时对人来说基本可以接受）
/// <summary>
/// https://leetcode-cn.com/problems/sudoku-solver/
/// </summary>
public class Solution
{
    private class Board
    {
        private readonly Square[,] squares = new Square[9, 9];

        public Square GetSquare(int row, int col)
        {
            return squares[row, col];
        }
        public bool TrySetValue(int row, int col, int value)
        {
            return squares[row, col].TrySetValue(value);
        }

        public Board()
        {
            // 0
            // 1
            // 2
            // 3
            // 4
            // 5
            // 6
            // 7
            // 8
            var rowBlocks = new Square.SquareBlock[9]
                {
                    new Square.SquareBlock(),
                    new Square.SquareBlock(),
                    new Square.SquareBlock(),
                    new Square.SquareBlock(),
                    new Square.SquareBlock(),
                    new Square.SquareBlock(),
                    new Square.SquareBlock(),
                    new Square.SquareBlock(),
                    new Square.SquareBlock(),
                };
            // 0 1 2 3 4 5 6 7 8
            var colBlocks = new Square.SquareBlock[9]
                {
                    new Square.SquareBlock(),
                    new Square.SquareBlock(),
                    new Square.SquareBlock(),
                    new Square.SquareBlock(),
                    new Square.SquareBlock(),
                    new Square.SquareBlock(),
                    new Square.SquareBlock(),
                    new Square.SquareBlock(),
                    new Square.SquareBlock(),
                };

            // 0 1 2
            // 3 4 5
            // 6 7 8
            var zoneBlocks = new Square.SquareBlock[9]
                {
                    new Square.SquareBlock(),
                    new Square.SquareBlock(),
                    new Square.SquareBlock(),
                    new Square.SquareBlock(),
                    new Square.SquareBlock(),
                    new Square.SquareBlock(),
                    new Square.SquareBlock(),
                    new Square.SquareBlock(),
                    new Square.SquareBlock(),
                };

            for (int i = 0; i < 9; i++)
            {
                squares[0, i] = new Square(rowBlocks[0], colBlocks[i], zoneBlocks[0 + i / 3]);
                squares[1, i] = new Square(rowBlocks[1], colBlocks[i], zoneBlocks[0 + i / 3]);
                squares[2, i] = new Square(rowBlocks[2], colBlocks[i], zoneBlocks[0 + i / 3]);
                squares[3, i] = new Square(rowBlocks[3], colBlocks[i], zoneBlocks[3 + i / 3]);
                squares[4, i] = new Square(rowBlocks[4], colBlocks[i], zoneBlocks[3 + i / 3]);
                squares[5, i] = new Square(rowBlocks[5], colBlocks[i], zoneBlocks[3 + i / 3]);
                squares[6, i] = new Square(rowBlocks[6], colBlocks[i], zoneBlocks[6 + i / 3]);
                squares[7, i] = new Square(rowBlocks[7], colBlocks[i], zoneBlocks[6 + i / 3]);
                squares[8, i] = new Square(rowBlocks[8], colBlocks[i], zoneBlocks[6 + i / 3]);
            }
        }

        public class Square
        {
            public class SquareBlock
            {
                public SquareBlock() { }

                /// <summary>
                /// 由 <see cref="Square"/> 类进行添加，完成构建后不应该再修改。
                /// </summary>
                public IList<Square> Squares { get; } = new List<Square>(9);

                public IEnumerable<int> GetAllUsedValue()
                {
                    return Squares.Select(item => item.Value);
                }

                public bool IsValueUsed(int value)
                {
                    if (value is >= 1 and <= 9)
                        return Squares.Select(item => item.Value).Contains(value);
                    return false;
                }
            }

            public Square(params SquareBlock[] blocks)
                : this(blocks.AsEnumerable()) { }

            public Square(IEnumerable<SquareBlock> blocks)
            {
                this.Blocks = blocks.ToArray();
                foreach (var block in blocks)
                    block.Squares.Add(this);
                this.Value = -1;
            }

            /// <summary>
            /// <code>-1</code> 表示没有填入。
            /// </summary>
            public int Value { get; private set; }

            public IEnumerable<SquareBlock> Blocks { get; }

            private readonly static Random r = new Random();

            private static readonly int[] from1To9 = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

            public bool TrySetRandomValue()
            {
                var allUsed = Blocks.SelectMany(block => block.GetAllUsedValue());
                var all = new List<int>(from1To9);
                foreach(var used in allUsed)
                {
                    _ = all.Remove(used);
                }
                if (all.Count == 0)
                    return false;
                this.Value = all[r.Next(0, all.Count)];
                return true;
            }

            public bool TrySetValue(int value)
            {
                if (value is >= 1 and <= 9)
                {
                    var isUsed = false;
                    foreach (var block in this.Blocks)
                    {
                        if (block.IsValueUsed(value))
                        {
                            isUsed = true;
                            break;
                        }
                    }
                    if (isUsed)
                        return false;
                    Value = value;
                    return true;
                }
                return false;
            }
            public void RemoveValue()
            {
                this.Value = -1;
            }
        }
    }
    public void SolveSudoku(char[][] board)
    {
        var sudukuBoard = new Board();
        List<Board.Square> squares = new List<Board.Square>(81);
        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                var c = board[i][j];
                var s = sudukuBoard.GetSquare(i, j);
                if (c != '.')
                    _ = s.TrySetValue(c - '0');
                else
                    squares.Add(s);
            }
        }

        bool bad = true;
        for (; bad;)
        {
            bad = false;
            foreach (var sqaure in squares)
            {
                if (!sqaure.TrySetRandomValue())
                    bad = true;
            }

            if (bad)
                foreach (var sqaure in squares)
                    sqaure.RemoveValue();

        }

        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                var c = sudukuBoard.GetSquare(i, j).Value;
                board[i][j] = (char)(c + '0');
            }
        }
    }
}
*/